Nonlinear eigenproblem
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
top
In mathematics, a nonlinear eigenproblem, sometimes nonlinear eigenvalue problem, is a generalization of the (ordinary) eigenvalue problem to equations that depend nonlinearly on the eigenvalue. Specifically, it refers to equations of the form
M ( λ λ ) x = 0 , {\displaystyle M(\lambda )x=0,}
where x ≠ ≠ 0 {\displaystyle x\neq 0} is a vector, and M {\displaystyle M} is a matrix-valued function of the number λ λ {\displaystyle \lambda } . The number λ λ {\displaystyle \lambda } is known as the (nonlinear) eigenvalue, the vector x {\displaystyle x} as the (nonlinear) eigenvector, and ( λ λ , x ) {\displaystyle (\lambda ,x)} as the eigenpair. The matrix M ( λ λ ) {\displaystyle M(\lambda )} is singular at an eigenvalue λ λ {\displaystyle \lambda } .
Contents
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Definition
In the discipline of numerical linear algebra the following definition is typically used.cite-ref-0-1-0[1]cite-ref-2[2]cite-ref-3[3]cite-ref-1-4-0[4]
Let Ω Ω ⊆ ⊆ C {\displaystyle \Omega \subseteq \mathbb {C} } , and let M : Ω Ω → → C n × × n {\displaystyle M:\Omega \rightarrow \mathbb {C} ^{n\times n}} be a function that maps scalars to matrices. A scalar λ λ ∈ ∈ C {\displaystyle \lambda \in \mathbb {C} } is called an eigenvalue, and a nonzero vector x ∈ ∈ C n {\displaystyle x\in \mathbb {C} ^{n}} is called a right eigenvector if M ( λ λ ) x = 0 {\displaystyle M(\lambda )x=0} . Moreover, a nonzero vector y ∈ ∈ C n {\displaystyle y\in \mathbb {C} ^{n}} is called a left eigenvector if y H M ( λ λ ) = 0 H {\displaystyle y^{H}M(\lambda )=0^{H}} , where the superscript H {\displaystyle ^{H}} denotes the Hermitian transpose. The definition of the eigenvalue is equivalent to det ( M ( λ λ ) ) = 0 {\displaystyle \det(M(\lambda ))=0} , where det ( ) {\displaystyle \det()} denotes the determinant.cite-ref-0-1-1[1]
The function M {\displaystyle M} is usually required to be a holomorphic function of λ λ {\displaystyle \lambda } (in some domain Ω Ω {\displaystyle \Omega } ).
In general, M ( λ λ ) {\displaystyle M(\lambda )} could be a linear map, but most commonly it is a finite-dimensional, usually square, matrix.
Definition: An eigenvalue λ λ {\displaystyle \lambda } is said to have algebraic multiplicity k {\displaystyle k} if k {\displaystyle k} is the smallest integer such that the k {\displaystyle k} th derivative of det ( M ( z ) ) {\displaystyle \det(M(z))} with respect to z {\displaystyle z} , in λ λ {\displaystyle \lambda } is nonzero. In formulas that d k det ( M ( z ) ) d z k | z = λ λ ≠ ≠ 0 {\displaystyle \left.{\frac {d^{k}\det(M(z))}{dz^{k}}}\right|_{z=\lambda }\neq 0} but d ℓ ℓ det ( M ( z ) ) d z ℓ ℓ | z = λ λ = 0 {\displaystyle \left.{\frac {d^{\ell }\det(M(z))}{dz^{\ell }}}\right|_{z=\lambda }=0} for ℓ ℓ = 0 , 1 , 2 , … … , k − − 1 {\displaystyle \ell =0,1,2,\dots ,k-1} .cite-ref-0-1-3[1]cite-ref-1-4-2[4]
Definition: The geometric multiplicity of an eigenvalue λ λ {\displaystyle \lambda } is the dimension of the nullspace of M ( λ λ ) {\displaystyle M(\lambda )} .cite-ref-0-1-4[1]cite-ref-1-4-3[4]
Special cases
The following examples are special cases of the nonlinear eigenproblem.
• The (ordinary) eigenvalue problem: M ( λ λ ) = A − − λ λ I . {\displaystyle M(\lambda )=A-\lambda I.}
• The generalized eigenvalue problem: M ( λ λ ) = A − − λ λ B . {\displaystyle M(\lambda )=A-\lambda B.}
• The quadratic eigenvalue problem: M ( λ λ ) = A 0 + λ λ A 1 + λ λ 2 A 2 . {\displaystyle M(\lambda )=A_{0}+\lambda A_{1}+\lambda ^{2}A_{2}.}
• The polynomial eigenvalue problem: M ( λ λ ) = ∑ ∑ i = 0 m λ λ i A i . {\displaystyle M(\lambda )=\sum _{i=0}^{m}\lambda ^{i}A_{i}.}
• The rational eigenvalue problem: M ( λ λ ) = ∑ ∑ i = 0 m 1 A i λ λ i + ∑ ∑ i = 1 m 2 B i r i ( λ λ ) , {\displaystyle M(\lambda )=\sum _{i=0}^{m_{1}}A_{i}\lambda ^{i}+\sum _{i=1}^{m_{2}}B_{i}r_{i}(\lambda ),} where r i ( λ λ ) {\displaystyle r_{i}(\lambda )} are rational functions.
• The delay eigenvalue problem: M ( λ λ ) = − − I λ λ + A 0 + ∑ ∑ i = 1 m A i e − − τ τ i λ λ , {\displaystyle M(\lambda )=-I\lambda +A_{0}+\sum _{i=1}^{m}A_{i}e^{-\tau _{i}\lambda },} where τ τ 1 , τ τ 2 , … … , τ τ m {\displaystyle \tau _{1},\tau _{2},\dots ,\tau _{m}} are given scalars, known as delays.
Jordan chains
Definition: Let ( λ λ 0 , x 0 ) {\displaystyle (\lambda _{0},x_{0})} be an eigenpair. A tuple of vectors ( x 0 , x 1 , … … , x r − − 1 ) ∈ ∈ C n × × C n × × ⋯ ⋯ × × C n {\displaystyle (x_{0},x_{1},\dots ,x_{r-1})\in \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{n}} is called a Jordan chain if ∑ ∑ k = 0 ℓ ℓ M ( k ) ( λ λ 0 ) x ℓ ℓ − − k = 0 , {\displaystyle \sum _{k=0}^{\ell }M^{(k)}(\lambda _{0})x_{\ell -k}=0,} for ℓ ℓ = 0 , 1 , … … , r − − 1 {\displaystyle \ell =0,1,\dots ,r-1} , where M ( k ) ( λ λ 0 ) {\displaystyle M^{(k)}(\lambda _{0})} denotes the k {\displaystyle k} th derivative of M {\displaystyle M} with respect to λ λ {\displaystyle \lambda } and evaluated in λ λ = λ λ 0 {\displaystyle \lambda =\lambda _{0}} . The vectors x 0 , x 1 , … … , x r − − 1 {\displaystyle x_{0},x_{1},\dots ,x_{r-1}} are called generalized eigenvectors, r {\displaystyle r} is called the length of the Jordan chain, and the maximal length a Jordan chain starting with x 0 {\displaystyle x_{0}} is called the rank of x 0 {\displaystyle x_{0}} .cite-ref-0-1-5[1]cite-ref-1-4-4[4]
Theorem:cite-ref-0-1-6[1] A tuple of vectors ( x 0 , x 1 , … … , x r − − 1 ) ∈ ∈ C n × × C n × × ⋯ ⋯ × × C n {\displaystyle (x_{0},x_{1},\dots ,x_{r-1})\in \mathbb {C} ^{n}\times \mathbb {C} ^{n}\times \dots \times \mathbb {C} ^{n}} is a Jordan chain if and only if the function M ( λ λ ) χ χ ℓ ℓ ( λ λ ) {\displaystyle M(\lambda )\chi _{\ell }(\lambda )} has a root in λ λ = λ λ 0 {\displaystyle \lambda =\lambda _{0}} and the root is of multiplicity at least ℓ ℓ {\displaystyle \ell } for ℓ ℓ = 0 , 1 , … … , r − − 1 {\displaystyle \ell =0,1,\dots ,r-1} , where the vector valued function χ χ ℓ ℓ ( λ λ ) {\displaystyle \chi _{\ell }(\lambda )} is defined as χ χ ℓ ℓ ( λ λ ) = ∑ ∑ k = 0 ℓ ℓ x k ( λ λ − − λ λ 0 ) k . {\displaystyle \chi _{\ell }(\lambda )=\sum _{k=0}^{\ell }x_{k}(\lambda -\lambda _{0})^{k}.}
Mathematical software
• The FEAST eigenvalue solver is a software package for standard eigenvalue problems as well as nonlinear eigenvalue problems, designed from density-matrix representation in quantum mechanics combined with contour integration techniques.cite-ref-7[7]
• The review paper of Güttel & Tisseurcite-ref-0-1-7[1] contains MATLAB code snippets implementing basic Newton-type methods and contour integration methods for nonlinear eigenproblems.
Eigenvector nonlinearity
Eigenvector nonlinearities is a related, but different, form of nonlinearity that is sometimes studied. In this case the function M {\displaystyle M} maps vectors to matrices, or sometimes hermitian matrices to hermitian matrices.cite-ref-13[13]cite-ref-14[14]
References
cite-note-0-11. ↑ citerefg-tteltisseur2017Güttel, Stefan; Tisseur, Françoise (2017). "The nonlinear eigenvalue problem" (PDF). Acta Numerica. 26: 1–94. doi:10.1017/S0962492917000034. ISSN 0962-4929. S2CID 46749298.
cite-note-33. ↑ citerefmehrmannvoss2004Mehrmann, Volker; Voss, Heinrich (2004). "Nonlinear eigenvalue problems: a challenge for modern eigenvalue methods". GAMM-Mitteilungen. 27 (2): 121–152. doi:10.1002/gamm.201490007. ISSN 1522-2608. S2CID 14493456.
cite-note-1-44. ↑ citerefvoss2014Voss, Heinrich (2014). "Nonlinear eigenvalue problems" (PDF). In Hogben, Leslie (ed.). Handbook of Linear Algebra (2 ed.). Boca Raton, FL: Chapman and Hall/CRC. ISBN 9781466507289.
cite-note-55. ↑ citerefhernandezromanvidal2005Hernandez, Vicente; Roman, Jose E.; Vidal, Vicente (September 2005). "SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems". ACM Transactions on Mathematical Software. 31 (3): 351–362. doi:10.1145/1089014.1089019. S2CID 14305707.
cite-note-66. ↑ citerefbetckehighammehrmannschr-der2013Betcke, Timo; Higham, Nicholas J.; Mehrmann, Volker; Schröder, Christian; Tisseur, Françoise (February 2013). "NLEVP: A Collection of Nonlinear Eigenvalue Problems". ACM Transactions on Mathematical Software. 39 (2): 1–28. doi:10.1145/2427023.2427024. S2CID 4271705.
cite-note-88. ↑ citerefg-ttelvan-beeumenmeerbergenmichiels2014Güttel, Stefan; Van Beeumen, Roel; Meerbergen, Karl; Michiels, Wim (1 January 2014). "NLEIGS: A Class of Fully Rational Krylov Methods for Nonlinear Eigenvalue Problems". SIAM Journal on Scientific Computing. 36 (6): A2842 – A2864. Bibcode:2014SJSC...36A2842G. doi:10.1137/130935045.
cite-note-1010. ↑ citereflietaertmeerbergenp-rezvandereycken2022Lietaert, Pieter; Meerbergen, Karl; Pérez, Javier; Vandereycken, Bart (13 April 2022). "Automatic rational approximation and linearization of nonlinear eigenvalue problems". IMA Journal of Numerical Analysis. 42 (2): 1087–1115. arXiv:1801.08622. doi:10.1093/imanum/draa098.
cite-note-1111. ↑ citerefberljafasteveng-ttel2020Berljafa, Mario; Steven, Elsworth; Güttel, Stefan (15 July 2020). "An overview of the example collection". index.m. Retrieved 31 May 2022.
cite-note-1313. ↑ citerefjarlebringkvaalmichiels2014Jarlebring, Elias; Kvaal, Simen; Michiels, Wim (2014-01-01). "An Inverse Iteration Method for Eigenvalue Problems with Eigenvector Nonlinearities". SIAM Journal on Scientific Computing. 36 (4): A1978 – A2001. arXiv:1212.0417. Bibcode:2014SJSC...36A1978J. doi:10.1137/130910014. ISSN 1064-8275. S2CID 16959079.
cite-note-1414. ↑ citerefupadhyayajarlebringrubensson2021Upadhyaya, Parikshit; Jarlebring, Elias; Rubensson, Emanuel H. (2021). "A density matrix approach to the convergence of the self-consistent field iteration". Numerical Algebra, Control & Optimization. 11 (1): 99. arXiv:1809.02183. doi:10.3934/naco.2020018. ISSN 2155-3297.
Further reading
• Françoise Tisseur and Karl Meerbergen, "The quadratic eigenvalue problem," SIAM Review 43 (2), 235–286 (2001) (link).
• Gene H. Golub and Henk A. van der Vorst, "Eigenvalue computation in the 20th century," Journal of Computational and Applied Mathematics 123, 35–65 (2000).
• Philippe Guillaume, "Nonlinear eigenproblems," SIAM Journal on Matrix Analysis and Applications 20 (3), 575–595 (1999) (link).
• Cedric Effenberger, "Robust solution methods fornonlinear eigenvalue problems", PhD thesis EPFL (2013) (link)
• Roel Van Beeumen, "Rational Krylov methods fornonlinear eigenvalue problems", PhD thesis KU Leuven (2015) (link)